package com.mango.leet.code.week2.game375;

import java.util.*;


/**
 * 100137. 统计最大元素出现至少 K 次的子数组
 * https://leetcode.cn/contest/weekly-contest-375/problems/count-subarrays-where-max-element-appears-at-least-k-times/
 */
public class LC100137 {
    /**
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * 思路：
     * 1. 找到最大数字max
     * 2. 从左到右遍历，如果x=max，则maxCount++;
     * 3. 如果maxCount==k，则left往右边移动，移动到max的数字则maxCount--;
     * 4. 结果加上left
     */
    public static long countSubarrays(int[] nums, int k) {
        int max = Arrays.stream(nums).max().getAsInt();
        long ans = 0;
        int maxCount = 0, left = 0;
        for (int x : nums) {
            if (x == max) {
                maxCount++;
            }
            while (maxCount == k) {
                if (nums[left++] == max) {
                    maxCount--;
                }
            }
            ans += left;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {1,4,2,1};
        int k = 3;
        int[] nums2 = {61,23,38,23,56,40,82,56,82,82,82,70,8,69,8,7,19,14,58,42,82,10,82,78,15,82};
        int k2 = 2;
        int[] nums3 = {1,3,2,3,3};
        int k3 = 2;
        //System.out.println(countSubarrays(nums, k));
        //System.out.println(countSubarrays(nums2, k2));
        System.out.println(countSubarrays(nums3, k3));
    }
}
